package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName LengthOfLongestSubstring
 * @Description LengthOfLongestSubstring
 * @Author wanghaiwei
 * @Date 2023/1/31 9:37
 */
public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        //使用maxLength记录最大的窗口大小
        int maxLength = 0;
        //使用HashMap记录重复字符的最大下标，用于确定窗口的左界下标
        Map<Character, Integer> winCharsMap = new HashMap<>();
        //滑动窗口的左界下标为winIdx，右界下标为i
        int winIdx = 0;
        //每次滑动窗口的大小，最大的那此滑动窗口的大小，就是答案
        int winSize = 0;
        for (int i = 0; i < s.length(); i++) {
            Character currChar = s.charAt(i);
            if (winCharsMap.containsKey(currChar)) {
                //窗口只会往右，意味着窗口的左界下标只会增大，不会变小，所以左界下标不会小于上一次的下标
                winIdx = Math.max(winCharsMap.get(currChar) + 1, winIdx);
                winSize = i - winIdx + 1;
            } else {
                winSize++;
            }
            //使用maxLength记录最大的窗口大小
            maxLength = Math.max(winSize, maxLength);
            winCharsMap.put(currChar, i);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        LengthOfLongestSubstring solution = new LengthOfLongestSubstring();
        int result = solution.lengthOfLongestSubstring("abcabcbb");
        Assert.isTrue(3 == result, "abcabcbb计算错误，预期3，实际：" + result);
        result = solution.lengthOfLongestSubstring("bbbbb");
        Assert.isTrue(1 == result, "bbbbb计算错误，预期1，实际：" + result);
        result = solution.lengthOfLongestSubstring("pwwkew");
        Assert.isTrue(3 == result, "pwwkew计算错误，预期3，实际：" + result);
        result = solution.lengthOfLongestSubstring(" ");
        Assert.isTrue(1 == result, "空计算错误，预期1，实际：" + result);
        result = solution.lengthOfLongestSubstring("dvdf");
        Assert.isTrue(3 == result, "dvdf计算错误，预期3，实际：" + result);
        result = solution.lengthOfLongestSubstring("abba");
        Assert.isTrue(2 == result, "abba计算错误，预期2，实际：" + result);
    }
}
